22. 1. 2009, O. Pangrác

1. Definujte bipartitní graf. Rozhodněte, zda je kružnice délky n bipartitním grafem.

2. Formulujte a dokažte větu o barevnosti rovinných grafů. (Věta o 5 barvách)

3. Kolik existuje uspořádaných dvojic (A,B) takových, že A i B jsou podmnožiny {1,2,...,n} a |A průnik B| = 1?

1. Kdy jsou dva jevy nezávislé (definice). Kdy jsou tři jevy nezávislé. Vymyslet příklad, kdy jsou tři jevy závislé, ale po dvojicích nezávislé.

2. nejlepší dolní odhad počtu navzájem neizomorfních grafů na n vrcholech + důkaz

3. zjistit počet koster grafu vzniklého z K4 dělením všech hran

1 - Definuj realnu nahodnu velicinu, definuj indikator javu
2 - Sformuluj vetu o barevnosti rovinnych grafov a dokaz
3 - Kolko najviac vrcholov s roznym stupnom moze byt na grafe s poctom vrcholov n.

(bolo to n-1, a vynimka ked je graf jediny vrchol, vtedy je to n)
(inac ako v pohode skuska :-) Pangrac je fajn, v 3. ulohe som spravil chybu takze mi dal
nahradny priklad - (co je to ekvivalencia, co je to rozkladova trieda, kolko roznych ekvivalencii je na stvroprvkovej mnozine

• vysledok sa vypocita pomocou kombinacnych cisel, o tom som ale nemal sajn, takze nakoniec za 2)

Jsem nějak mimo, jak se tohle řeší, poradí někdo?

Kolik existuje uspořádaných dvojic (A,B) takových, že A i B jsou podmnožiny {1,2,...,n} a |A průnik B| = 1?

|A prienik B|=1 =>existuje n roznych prienikov (1,2,3...)
Ak uz mam zvolene cislo ktore bude prienikom ostava mi n-1 cisel x a pre kazde z nich plati:
(x patri A) xor (x patri B) xor (x nepatri ani A ani B) teda pre kazde z tych n-1 existuju 3 moznosti ako sa chovat, teda vzorec je
n.3^(n-1)

Díky, takhle to už vypadá jednoduše. Musím prostě víc cvičit...